package classic;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-12-22 14:29
 **/
public class KMP {


    public int strStr(String haystack, String needle) {
         int m = haystack.length();
         int n = needle.length();

         //如果needle是空字符,返回0,和Java中的indexOf方法一只
         if (n == 0) {
             return 0;
         }

         //获取next数组
         int[] next = getNext(needle);

         for (int i = 0, j = 0; i < m; ++i) {
             //如果haystack在i处的字符与needle在j处的字符不匹配,j向前回溯到匹配的位置或者开头
             while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {
                 j = next[j - 1];
             }

             //如果匹配j++
             if (haystack.charAt(i) == needle.charAt(j)) {
                 ++j;
             }

             //j==n说明匹配完毕,i-n+1haystack与needle开始匹配的索引
             if (j == n) {
                 return i - n + 1;
             }
         }

         return -1;
    }

    /**
     * 获取某一个字符串的next数组
     * @param str
     * @return
     */
    int[] getNext(String str) {
        int m = str.length();
        int[] next = new int[m];
        for (int i = 0, j = 1; j < m; ++j) {
            //如果i,j字符不匹配,向前回溯到匹配的位置
            while (i > 0 && str.charAt(i) != str.charAt(j)) {
                i = next[i - 1];
            }

            //如果匹配i++
            if (str.charAt(i) == str.charAt(j)) {
                ++i;
            }

            //next[j]:表示如果j + 1处的字符不匹配应该回溯到的位置
            next[j] = i;
        }

        return next;
    }

}
